home *** CD-ROM | disk | FTP | other *** search
/ Aminet 1 (Walnut Creek) / Aminet - June 1993 [Walnut Creek].iso / aminet / gfx / misc / pchglib12.lha / HuffComp.c < prev    next >
C/C++ Source or Header  |  1992-11-15  |  7KB  |  231 lines
  1. #include <exec/types.h>
  2. #include <proto/exec.h>
  3. #include <exec/memory.h>
  4. #include <iff/pchg.h>
  5. #include <clib/pchglib_protos.h>
  6.  
  7. #if INCLUDE_VERSION<36
  8. FAILURE!! Amiga includes version<36
  9. #endif
  10.  
  11.  
  12. /* The following structures are used by pchg.lib, and shouldn't be used by
  13. any other program. */
  14.  
  15. struct TreeInternalNode {
  16.     struct TreeNode *Left;
  17.     struct TreeNode *Right;
  18. };
  19.  
  20. struct TreeExternalNode {
  21.     ULONG CodeLength;
  22.     ULONG Code;
  23. };
  24.  
  25. struct TreeNode {
  26.     struct TreeNode *Parent;
  27.     UWORD IsExternal;
  28.     UWORD IsRight;
  29.     union {
  30.         struct TreeInternalNode Int;
  31.         struct TreeExternalNode Ext;
  32.     } n;
  33. };
  34.  
  35. struct CompVars {
  36.     ULONG Freq[256];
  37.     struct TreeNode Nodes[511], *N[256];
  38.     UWORD TreeCode[511];
  39. };
  40.  
  41. VOID __asm PCHG_BuildFreqTable(register __a0 APTR Source, register __d0 ULONG Length, register __a1 ULONG *FreqTable);
  42.  
  43.  
  44. /* This function takes a tree represented with TreeNode structures,
  45. and sets the Code and CodeLength fields of its internal nodes. If
  46. the CodeLength fields are previously filled with the frequency
  47. of the associated character, the total length in bits of the
  48. compressed data will be returned. Note that if the CodeLength is
  49. greater than 32, Code is useless. */
  50.  
  51.  
  52. ULONG PCHG_SetUpTree(struct TreeNode *Tree, ULONG Depth, ULONG Bits) {
  53.     if (Tree->IsExternal) {
  54.         Tree->n.Ext.Code = Bits;
  55.         Bits = Tree->n.Ext.CodeLength*Depth;
  56.         Tree->n.Ext.CodeLength = Depth;
  57.         return(Bits);
  58.     }
  59.     return(PCHG_SetUpTree(Tree->n.Int.Left, Depth+1, Bits<<1)+PCHG_SetUpTree(Tree->n.Int.Right, Depth+1, Bits<<1 | 1));
  60. }
  61.  
  62. /* This function converts a tree represented via TreeNodes in
  63. a tree code ready for writing it in a PCHG compressed chunk. The
  64. real length in bytes of the tree is returned */
  65.  
  66. LONG PCHG_BuildTreeCode(struct TreeNode *Tree, WORD *TreeCode) {
  67.     register LONG t;
  68.  
  69.     if (Tree->IsExternal) {
  70.         *TreeCode = (unsigned char)Tree->IsExternal | 0x100;
  71.         return(1);
  72.     }
  73.     t = PCHG_BuildTreeCode(Tree->n.Int.Left, TreeCode-1);
  74.     if (Tree->n.Int.Right->IsExternal) {
  75.         *TreeCode = (unsigned char)Tree->n.Int.Right->IsExternal;
  76.         return(t+1);
  77.     }
  78.     *TreeCode = (-t-1)*2;
  79.     return(t+1+PCHG_BuildTreeCode(Tree->n.Int.Right, TreeCode-t-1));
  80. }
  81.  
  82. /* The compression routine. Given the tree in linked form, source
  83. and destination it performs the compression. */
  84.  
  85. ULONG PCHG_Compress(UBYTE *Source, ULONG *Dest, struct TreeNode *ExtNodes, ULONG SourceLen) {
  86.  
  87.     register LONG i;
  88.     LONG j;
  89.     register LONG codelen, freebits = 32;
  90.     register UBYTE c;
  91.     register ULONG CurLongword = 0;
  92.     ULONG *StartDest = Dest;
  93.     struct TreeNode *Tree;
  94.  
  95.     for(i=0; i<SourceLen; i++) {
  96.         if ((codelen = ExtNodes[c = *(Source++)].n.Ext.CodeLength)<33) {
  97.             if (codelen>freebits) {
  98.                 if (!freebits) {
  99.                     *(Dest++) = CurLongword;
  100.                     CurLongword = ExtNodes[c].n.Ext.Code<<(freebits = 32-codelen);
  101.                 }
  102.                 else {
  103.                     *(Dest++) = CurLongword | ExtNodes[c].n.Ext.Code>>(codelen-freebits);
  104.                     CurLongword = ExtNodes[c].n.Ext.Code<<(freebits += 32-codelen);
  105.                 }
  106.             }
  107.             else {
  108.                 CurLongword |= ExtNodes[c].n.Ext.Code<<(freebits-=codelen);
  109.             }
  110.         }
  111.         else {
  112.             Tree = &ExtNodes[c];
  113.             *Dest = CurLongword;
  114.             freebits = 32-freebits;
  115.             for(j=codelen-1; j>=0; j--) {
  116.                 Dest[(freebits+j)/32] |= Tree->IsRight << (31-((freebits+j)%32));
  117.                 Tree = Tree->Parent;
  118.             }
  119.             Dest += (freebits+codelen)/32;
  120.             CurLongword = *Dest;
  121.             freebits = 32-((freebits+codelen)%32);
  122.         }
  123.     }
  124.     if (freebits != 32) *(Dest++) = CurLongword;
  125.     return((ULONG)(Dest-StartDest)*4);
  126. }
  127.  
  128. /****** pchg.lib/PCHG_CompHuffmann ******************************************
  129.  
  130.    NAME
  131.        PCHG_CompHuffmann -- Compress a memory block with static Huffmann
  132.  
  133.    SYNOPSIS
  134.        compData = CompHuffmann(Source, SourceSize, DataSize, TreeSize);
  135.  
  136.        UBYTE *PCHG_CompHuffmann(APTR, ULONG, ULONG *, ULONG *);
  137.  
  138.    FUNCTION
  139.        Compress a block of memory into the typical PCHG compression
  140.        format: static Huffmann encoding. A pointer to the compressed data
  141.        (tree+code) is returned. After use, the block of
  142.        *DataSize+*TreeSize length pointed by compData has to be
  143.        FreeMem()ed. The longword pointed by TreeSize will be set to the
  144.        number of bytes used by the tree coding, the one pointed by DataSize
  145.        to the number of bytes of Huffmann code (rounded to longword bounds).
  146.  
  147.    INPUTS
  148.        Source        - A pointer to the start of the data to be compressed.
  149.        SourceSize    - Size in bytes of the data to be compressed
  150.        DataSize      - A pointer to a longword that will receive the length
  151.                        in bytes of the data part of the compressed chunk.
  152.        TreeSize      - A pointer to a longword that will receive the length
  153.                        in bytes of the tree part of the compressed chunk.
  154.  
  155.    RESULT
  156.        compData      - A pointer to the compressed data (tree+data,
  157.                        *DataSize+*TreeSize bytes) or NULL if a
  158.                        memory allocation failed. You have to free
  159.                        this memory after you use it with a
  160.                        FreeMem(compData, *TreeSize+*DataSize).
  161.  
  162.    EXAMPLE
  163.  
  164.    NOTES
  165.  
  166.    BUGS
  167.  
  168.    SEE ALSO
  169.        PCHG_FastDecomp(), PCHG_CFastDecomp()
  170.  
  171. *****************************************************************************
  172. *
  173. */
  174.  
  175. UBYTE *PCHG_CompHuffmann(APTR Source, ULONG SourceSize, ULONG *DataSize, ULONG *TreeSize) {
  176.  
  177.     register LONG i,j;
  178.     register UBYTE *p;
  179.     register struct CompVars *cv;
  180.     struct TreeNode *Tree;
  181.     ULONG LastMin0, LastMin1, LastMinVal0, LastMinVal1;
  182.  
  183.     if (!(cv = AllocMem(sizeof(struct CompVars), MEMF_PUBLIC | MEMF_CLEAR))) return(NULL);
  184.  
  185.     PCHG_BuildFreqTable(Source, SourceSize, cv->Freq);
  186.  
  187.     for(i=0; i<256; i++) {
  188.         cv->Nodes[i].n.Ext.CodeLength = cv->Freq[i];
  189.         cv->Nodes[i].IsExternal = i | (1<<15);
  190.         cv->N[i] = &cv->Nodes[i];
  191.     }
  192.  
  193.     for(i=1; i<256; i++) {
  194.  
  195.         LastMinVal0 = LastMinVal1 = 0xFFFFFFFFU;
  196.  
  197.         for(j=i-1; j<256; j++)
  198.             if (cv->Freq[j]<LastMinVal0) {
  199.                 LastMinVal0 = cv->Freq[j];
  200.                 LastMin0 = j;
  201.             }
  202.         cv->Freq[LastMin0] = cv->Freq[i-1];
  203.         cv->Freq[i-1] = LastMinVal0;
  204.         Tree = cv->N[i-1];
  205.         cv->N[i-1] = cv->N[LastMin0];
  206.         cv->N[LastMin0] = Tree;
  207.  
  208.         for(j=i; j<256; j++)
  209.             if (cv->Freq[j]<LastMinVal1) {
  210.                 LastMinVal1 = cv->Freq[j];
  211.                 LastMin1 = j;
  212.             }
  213.         cv->Freq[LastMin1] = LastMinVal0+LastMinVal1;
  214.         cv->Nodes[255+i].n.Int.Left = cv->N[i-1];
  215.         cv->Nodes[255+i].n.Int.Right = cv->N[LastMin1];
  216.         cv->N[i-1]->Parent = cv->N[LastMin1]->Parent = &cv->Nodes[255+i];
  217.         cv->N[LastMin1]->IsRight = 1;
  218.         cv->N[LastMin1] = &cv->Nodes[255+i];
  219.     }
  220.  
  221.     *DataSize = ((PCHG_SetUpTree(&cv->Nodes[510], 0, 0)+31)/32)*4;
  222.     *TreeSize = 2*PCHG_BuildTreeCode(&cv->Nodes[510], &cv->TreeCode[510]);
  223.  
  224.     if (p = AllocMem(*DataSize+*TreeSize, MEMF_PUBLIC | MEMF_CLEAR)) {
  225.         CopyMem(&cv->TreeCode[510]-(*TreeSize/2-1), p, *TreeSize);
  226.         PCHG_Compress(Source, (void  *)(p+*TreeSize), cv->Nodes, SourceSize);
  227.     }
  228.     FreeMem(cv, sizeof(struct CompVars));
  229.     return(p);
  230. }
  231.